const arr1 = [2, 1, 4, 7, 6];

// 1 0   1
// 2 1 0   2
// 3 2 1 0  3
// 4 3 2 1 0 4

// 方法一：
// for (let i = 0; i < arr1.length; i++) {
//   let jLength = i + 1;
//   for (let j = jLength; j > -1; j--) {
//     const temp1 = arr1[j];
//     const temp2 = arr1[jLength];
//     if (arr1[jLength] < arr1[j]) {
//       arr1[j] = temp2;
//       arr1[jLength] = temp1;
//     }
//   }
// }

// 方法二：
// for (let i = 0; i < arr1.length; i++) {
//   let jLength = i + 1;
//   let j = i;
//   while (j > -1 && j < jLength) {
//     if (arr1[jLength] < arr1[j]) {
//       const temp1 = arr1[j];
//       const temp2 = arr1[jLength];
//       arr1[j] = temp2;
//       arr1[jLength] = temp1;
//     }
//     j -= 1;
//   }
// }

// 方法二优化
// for (let i = 0; i < arr1.length; i++) {
//   let jLength = i + 1;
//   let j = i;
//   let temp = arr1[jLength];
//   let index = -1;
//   while (j > -1 && j < jLength) {
//     if (temp < arr1[j]) {
//       arr1[jLength] = arr1[j];
//       index = j;
//     }
//     j -= 1;
//   }

//   if (index !== -1) {
//     arr1[index] = temp;
//   }
// }

// 方式四
function insertSort(arr) {
  // 缓存数组长度
  const len = arr.length
  // temp 用来保存当前需要插入的元素
  let temp  
  // i用于标识每次被插入的元素的索引
  for(let i = 1;i < len; i++) {
    // j用于帮助 temp 寻找自己应该有的定位
    let j = i
    temp = arr[i]  
    // 判断 j 前面一个元素是否比 temp 大
    while(j > 0 && arr[j-1] > temp) {
      // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
      arr[j] = arr[j-1]   
      j--
    }
    // 循环让位，最后得到的 j 就是 temp 的正确索引
    arr[j] = temp
  }
  return arr


// function insertSort(arr) {
//   // 缓存数组长度
//   const len = arr.length;
//   // temp 用来保存当前需要插入的元素
//   let temp;
//   // i用于标识每次被插入的元素的索引
//   for (let i = 1; i < len; i++) {
//     // j用于帮助 temp 寻找自己应该有的定位
//     let j = i;
//     temp = arr[i];
//     // 判断 j 前面一个元素是否比 temp 大
//     while (j > 0 && arr[j - 1] > temp) {
//       // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
//       arr[j] = arr[j - 1];
//       j--;
//     }
//     // 循环让位，最后得到的 j 就是 temp 的正确索引
//     arr[j] = temp;
//   }
//   return arr;
// }

// console.log(newArr);
